#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <stdbool.h>

static int
cmpintp(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 选取pivot，把它放在该放的位置
int partition(int num[], int low, int high)
{
    int pivot_position = low;
    while(low < high) {
        while (low < high && num[pivot_position] <= num[high]) high--;
        swap(&num[pivot_position], &num[high]);
        pivot_position = high;
        while (low < high && num[pivot_position] >= num[low]) low++;
        swap(&num[pivot_position], &num[low]);
        pivot_position = low;
    }
    return pivot_position;
}

void quicksort(int num[], int low, int high)
{
    if(low < high){
        int pivot_position = partition(num, low, high);
        quicksort(num, low, pivot_position-1);
        quicksort(num, pivot_position+1, high);
    }
}

bool test_quicksort(int num[], int len)
{
    srand((unsigned)time(NULL));
    for (int i = 0; i < len; i++){
        num[i] = rand() % 100;
    }
    int num2[len];
    memcpy(num2, num, len * sizeof(int));
    qsort(num2, len, sizeof(int), cmpintp);
    quicksort(num, 0, len-1);
    for(int i=0;i<len;i++){
        if(num[i]!=num2[i]) return false;
    }
    return true;
}
int main(void)
{
    int len = 30;
    int num[len];
    int count = 1 << 10;
    for(int i=0; i<count; i++){
        if(!test_quicksort(num, len)){
            printf("failure\n");
            return -1;
        }
    }
    printf("sucess\n");
    return 0;
}